
public class InsertionSort extends Sort {
	
	//鐩存帴鎻掑叆鎺掑簭
	void sort() {
		System.out.println("鍘熷鏁扮粍搴忓垪");
		printArray();
		int j;
		for(int i=1; i<m_count; ++i) {
			m_next.assign(m_array[i]);
			
			for(j=i-1; j>=0 && m_next.lt(m_array[j]); --j) {
				m_array[j+1].assign(m_array[j]);
			}
			m_array[j+1].assign(m_next);
			System.out.println("寮�瀵筊" + i + "杩涜鎺掑簭锛屾帓搴忓悗缁撴灉濡備笅");
			printArray();
		}
		
	}

	//鎶樺崐鎻掑叆鎺掑簭
	void binSort() {
		int low, high, pivot;
		
		for(int i=1; i<m_count; ++i) {
			m_next.assign(m_array[i]);
			
			low = 0; 
			high = i - 1;
			while(low <= high) {
				pivot = (low+high)/2;
				if (m_next.ge(m_array[pivot])) low = pivot + 1;
				else high = pivot - 1;
			}
			
			int j;
			for(j=i; j>low; --j) {
				m_array[j].assign(m_array[j-1]);
			}
			m_array[j].assign(m_next);
		}
	}
	
	//閾捐〃鎻掑叆鎺掑簭
	void listSort() {
		int start = 0;
		m_array[start].setLink(-1);
		
		System.out.println("start: " + start);
		System.out.println("鍘熷鏁扮粍搴忓垪");
		printArray();
		printList();
		for(int i=1; i<m_count; ++i) {
			
			if (m_array[i].lt(m_array[start])) {
				m_array[i].setLink(start);
				start = i;
			} else {
				int j = start;
				int pos = j;
				while(m_array[i].ge(m_array[j])) {
					pos = j;
					j = m_array[j].getLink();
					if (j == -1) break;
				}
				m_array[pos].setLink(i);
				m_array[i].setLink(j);
			}
			System.out.println("start: " + start);
			System.out.println("寮�瀵筊" + i + "杩涜鎺掑簭锛屾帓搴忓悗缁撴灉濡備笅");
			printArray();
			printList();
		}
		
		for(int i=0; i<m_count; ++i) {
			while(start < i) {
				start = m_array[start].getLink();
			}
			System.out.println("琚氦鎹綅缃� " + start);
			if (m_array[start].lt(m_array[i])) {
				int next_start = m_array[start].getLink();
				m_array[start].swap(m_array[i]);
				
				m_array[i].setLink(start);
				start = next_start;
			}
			
			System.out.println("寮�瀵筊" + i + "杩涜浜ゆ崲锛屾帓搴忓悗缁撴灉濡備笅");
			printArray();
			printList();
		}
	}
	
	//鏄犲皠琛ㄦ彃鍏ユ帓搴�
	void tableSort() {	
		System.out.println("鍘熷鏁扮粍搴忓垪");
		printArray();
		printTable();
		for(int i=1; i<m_count; ++i) {
			m_array[i].setTable(i);
			
			int j = i;
			while(m_array[i].lt(m_array[m_array[j-1].getTable()])) {
				m_array[j].setTable(m_array[j-1].getTable());
				if (--j == 0) break;
			}
			m_array[j].setTable(i);
			System.out.println("寮�瀵筊" + i + "杩涜鎺掑簭锛屾帓搴忓悗缁撴灉濡備笅");
			printArray();
			printTable();
		}
		
		for(int i=0; i<m_count; ++i) {
			if (m_array[i].getTable() != i) {
				m_next.assign(m_array[i]);
				int j = i;
				int next;
				int next_next;
				do {
					next = m_array[j].getTable();
					next_next = m_array[next].getTable();
					m_array[j].assign(m_array[next]);
					m_array[j].setTable(j);
					j = next;
				} while(m_array[next_next].getTable() != next_next);
				m_array[j].assign(m_next);
				m_array[j].setTable(j);
				
				printArray();
				printTable();
			}
		}
	}
	
	//甯屽皵鎺掑簭
	void shellSort() {
		System.out.println("鍘熷鏁扮粍搴忓垪");
		printArray();
		
		int d = m_count / 2;
		while(d >= 1) {
			for(int i=d; i<m_count; ++i) {
				int j = i;
				while(m_array[j].lt(m_array[j-d])) {
					//System.out.println(j + " " + m_array[j].getKey() + " " + m_array[j-d].getKey());
					m_array[j].swap(m_array[j-d]);
					j -= d;
					if (j-d < 0) break;
				}
			}
			System.out.println("澧為噺d:" + d + " 鎺掑簭鍚庣粨鏋滃涓");
			printArray();
			d /= 2;
		}
	}
}

